package version2024.medium;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ103 Redraiment的走法  动态规划
 * @Date: created in 2025/1/9 星期四 16:35
 * @Modified By:
 */
public class HJ103_RedraimentMove {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();

            Integer n = Integer.valueOf(a);

            int[] nums = new int[n];

            String[] items = b.split(" ");

            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(items[i]);
            }

            // 2 5 1 5 4 5
            // dp
            // 0 1 2 3 4 5
            // 1 2 1 2 2 3
            // dp[i]表示到元素i结尾时，最长的子序列的长度
            int[] dp = new int[nums.length];
            // baseCase, 任何单字符构成一个子序列
            Arrays.fill(dp, 1);
            int max = 1;

            for (int i = 1; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[j] < nums[i]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                    max = Math.max(dp[i], max);
                }
            }

            System.out.println(max);
        }
    }
}
